package 蓝桥真题;

import java.util.Arrays;
//dp
public class 质数差分 {
       final static int N=3000;
       static int primers[]=new int[N],cnt,n;
       static long dp[][]=new long[N][N];
       static boolean st[]=new boolean[N];
       public static void main(String[] args) {
		      n=2019;
		      for(int i=2;i<=n;i++){
		    	  if(!st[i])primers[++cnt]=i;
		    	  for(int j=1;primers[j]<=n/i;j++){
		    		  st[primers[j]*i]=true;
		    		  if(i%primers[j]==0)break;
		    	  }
		      }
		      dp[0][0]=1;
		      for(int i=1;i<=cnt;i++)
		    	  for(int j=0;j<=n;j++){
		    		  dp[i][j]=dp[i-1][j];
		    		  if(primers[i]<=j)
		    			  dp[i][j]=dp[i-1][j]+dp[i-1][j-primers[i]];
		    	  }
		      System.out.print(dp[cnt][2019]);
	}
}
